The present invention relates generally to communication networks, and, more particularly, to routing of best-effort and quality-of-service flows in a communication network.
In packet networks such as the Internet, a simple static shortest path routing algorithm is commonly employed. A packet is sent on the shortest path to the destination. To determine the shortest path each link is assigned a weight and the shortest path is the one with the smallest aggregate weight. If there are multiple shortest paths, the shortest path is chosen arbitrarily. The key characteristic of this routing scheme is that the weights are assigned statically. The routes are staticxe2x80x94not in the sense that the routes cannot changexe2x80x94but in the sense that the routes are load insensitive. Hence, route changes occur only when a change in the topology of the network occurs, i.e. a link is deleted or added. This topology-driven static shortest path routing may suffice in networks that provide a single best effort service in which there is no guarantee about whether and when a packet will be delivered. It may, however, not be adequate in networks that wish to provide Quality of Service (xe2x80x9cQoSxe2x80x9d) guarantees. For example, with reference to FIG. 1, consider if a network 100 provided bandwidth guarantees to a flow. A flow, as is known in the art, is a sequence of packets from a source to a destination and, or our purposes, is synonymous with a connection. Assuming each link specified in FIG. 1 is given an identical weight, all flows originating from node 101 and destined to 105 will be routed over path 101-102-103-104-105. If a large number of flows originating from 101 and terminating at 105 request guaranteed bandwidth, then the links 102-103 and 103-104 may get saturated and flows may be denied their request. This may occur even though the alternate path 101-102-106-107-104-105 between 101 and 105 may have the capacity to support the flows that have been denied their request.
In order to exploit the available capacity on alternate routes, the concept of QoS routing has been proposed. See, e.g., E. Crawley et al., xe2x80x9cA Framework for QoS Based Routing in the Internet,xe2x80x9d RFC 2386, IETF Network Working Group, August 1998; R. Guerin et al., xe2x80x9cQoS Routing Mechanisms and OSPF Extensions,xe2x80x9d RFC 2676, IETF Network Working Group, August 1999, both of which are incorporated herein by reference. There are a large number of QoS routing algorithms. The characteristic common to all of these schemes is that they employ dynamically obtained information about load at each of the links to determine the path over which a flow should be routed. The path of a flow may be determined by source routing in which a flow setup message carries the entire path for the flow or by hop-by-hop routing. QoS routing algorithms have a few limitations.
First, in order to route packets of flows with the same destination over multiple routes, they require a connection-oriented network layer (i.e., the ability to xe2x80x9cpinxe2x80x9d the path of a flow). Thus, it is difficult to employ them in connectionless networks such as the Internet without substantial modifications to the basic architecture. Second, they can introduce routing and load oscillations resulting in higher instability in the performance seen by best-effort traffic. To illustrate, when the path 101-102-103-104 becomes loaded in FIG. 1, traffic will be diverted onto path 101-102-106-107-104. This will increase the load on path 101-102-106-107-104. Subsequently, when the load on path 101-102-103-104 reduces, the traffic will again be diverted onto path 101-102-103-104. Thus, the best effort traffic flowing on those two paths will observe high instability in the performancexe2x80x94which is undesirable.
Accordingly, there is a substantial need for introducing new ways of routing QoS and best effort flows that avoids the disadvantages of the prior art.
The present invention permits quality-of-service routing without using any flow pinning or per-flow state mechanisms. In accordance with the present invention, load insensitive routing techniques are utilized for QoS traffic while load sensitive routing techniques are utilized for best effort traffic. In accordance with a preferred embodiment of the present invention, conventional static shortest path routing is utilized for flows that require QoS guarantees while known QoS routing techniques are utilized for best effort flows. Unlike the prior art, a single queue per class per link can be utilized at a network node. The present invention has numerous advantages over the prior art including reduced protocol overhead, lower cost, and reduced route instability.
These and other advantages of the invention will be apparent to those of ordinary skill in the art by reference to the following detailed description and the accompanying drawings.